package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 */
public class Title235 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = null;
        TreeNode right = null;
        if (root.val > p.val || root.val > q.val) {
            left = lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < p.val || root.val < q.val) {
            right = lowestCommonAncestor(root.right, p, q);
        }
        if (left == null && right == null) {
            return null;
        } else if (left != null && right != null) {
            return root;
        } else if (left == null && right != null) {
            return right;
        }else{
            return left;
        }
    }




    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = null, right = null;
        if (root.val > p.val || root.val > q.val) {
            left = lowestCommonAncestor2(root.left, p, q);
        }
        if (root.val < p.val || root.val < q.val) {
            right = lowestCommonAncestor2(root.right, p, q);
        }
        if (left != null && right != null) {
            return root;
        } else if (left == null && right != null) {
            return right;
        } else if (left != null) {
            return left;
        }else{
            return null;
        }
    }

    public static void main(String[] args) {

    }
}
